Vue 源码解析之AST抽象语法树

您所在的位置：网站首页 › vue vdom源码 › Vue 源码解析之AST抽象语法树

Vue 源码解析之AST抽象语法树

2023-09-01 20:58| 来源: 网络整理| 查看: 265

Vue源码解析之AST抽象语法树.png 在面试的过程中，AST抽象语法树也是面试的高频知识，本文章我们会亲自手写实现抽象语法树，让你真正的理解 AST抽象语法树。开始手写 AST抽象语法树之前，我们先要了解3个常见的算法思想：指针思想、递归缓存和栈。然后利用这些算法思想，实现 AST抽象语法树。读完这篇文章，相信你的算法水平会有质的飞跃！！说不多说，直接进入正题！！

抽象语法树是什么

在模板语法中（如v-for循环中）如果我们直接将模板语法编译成正常的HTLM语法是非常困难的。

所以，我们需通过AST抽象语法树，将模板语法转换成正常的HTML语法，如下图所示

那么AST抽象语法树到底是什么呢？其实AST抽象语法树本质上是一个JS对象

上面图中，用JS结构来表示HTML结构实际上就是AST抽象语法树。抽象语法树是服务于模板编译的，从一种语法翻译成另外一种语法，比如 ES6 转 ES5

抽象语法树与虚拟节点的关系虚拟DOM 其实就是一个普通的JS对象，是为了提高页面渲染的性能而存在的。虚拟DOM 是通过 h函数生产一个虚拟状态的DOM,然后根据虚拟节点进行渲染，首次渲染的就会直接渲染，但是二次往后的话就是进行虚拟DOM的对比，只更新不同的地方。换成AST的是Vue模板，Vue需要根据模版去处理各种插值、指令；生成虚拟DOM的是最终要展示在页面上的内容的对象描述，Vue 每次需要通过 diff算法对比新旧虚拟DOM 的差异；固定模版生成的AST是不变的，虚拟DOM是不断变化、需要进行差异对比的（数据等会变）。渲染函数（h函数）,它既是AST的产物，也是vnode(虚拟节点)的起源。h函数里面是不含指令的。抽象语法树不会进行 diff算法的并且抽象语法树不会直接生成虚拟节点，抽象语法树最终生成的是渲染函数

模板语法先转换成抽象语法树，然后抽象语法树最后会直接变成渲染函数（h函数）。而渲染函数的执行会生成虚拟节点，虚拟节点经过 diff等算法，将虚拟DOM 变成真实DOM 从而在页面进行展示。

相关算法储备指针思想试找出字符串中，连续重复次数最多的字符 'aaaabbbbcccccccdddd'

解题思路：看到这个题目，我们只需要用生活中的常识就可以解决问题，一只手指指向第一个字符，另外一个手指从第二个开始，然会逐一往后与第一个进行比较，如果相同则，第一个手指不移动，如果不相同，第一个手指移动到的第二个手指指向的位置，然后继续上面的操作即可。这里可以使用双指针，i和j分别代表着两只手指，i=0，j=1

如果 i 和 j 指向的字一样，那么 i 不移动，j 后移如果 i 和 j 指向的字不一样，此时说明它们之间的字都是连续相同的，让 i 追上 j，j 后移有了上面的解题思路，我们就看编写代码了： const str = 'aaaaaabbbbbccccccccccccccccccddddd' let i = 0 let j = 1 let max = 0 // 记录出现最多的次数 let strChar = '' // 记录出现最多次数的字符 while(i max) { max = j - i strChar = str[i] } i = j } // 无论是否相同 j都要后移 j++ }

总结：其实，指针的问题都是源于我们生活中的常识，快速的找到匹配的结果，一般都可以用指针解题思路来解决问题。

递归 1、试输出斐波那契数列的前10项，即1、1、2、3、5、8、13、21、34、55，然后请思考，代码是否有大量重复计算？应该如何解决重复计算的问题？

解题思路：通过观察我们可以发现，第一项和第二项均为1，第三项等于前两项相加，后一项等于前两项相加，代码如下：

// 斐波那契数列输出前十项 function fib (n) { return (n == 0 || n==1) ? 1: fib(n-1) + fib(n-2) } for(let i = 0; i { console.log(...args); })

match（）方法

找出第一个符号正则条件的下标位置，并且返回一个数组，在全局的情况下会返回全部符合条件的下标位置并组成一个数组返回。

let str = 'ansbsda112fasf578' let num = str.match(/\d/) console.log(num);

let str = 'ansbsda112fasf578' let num = str.match(/\d/g) console.log(num);

test（）方法

test 检测字符串是否符合当前正则表达式

search（）方法

找出第一个符号正则条件的下标位置，返回下标，在全局的情况下也只会返回第一个符合条件的下标位置。

let str = 'ansbsda112fasf578' // let num = str.search(/\d/) // 7 let num = str.search(/\d/g) // 7 console.log(num); // 7

了解了正则表达式中常用的方法之后，我们正式来讲解一下题目的解题思路：上面分析我们知道，不能使用递归的方式来解决问题，我们需要通过栈的思想来进行解答，首先需要两个栈stack1和stack2，一个用来存储数字，一个用来存储字符串。

遍历每一个字符串如果这个字符是数字，那么就将数字压入 stack1栈，把空字符串压入stack2栈，如果这个字符是字母，那么此时就把stack2栈顶这一项改为这个字母，如果这个字符是]，那么就将数字从 stack1 栈中弹出，把 stack2的栈顶元素重复 stack1中弹栈的数字的次数，然后将其从stack2中弹出，拼接到stack2的新栈顶上。

分析了思路之后，相关代码如下：

function smartRepeat(templateStr) { // 指针 var index = 0 // 栈1 var stack1 = [] // 栈2 var stack2 = [] // 尾部 var rest = templateStr while(index < templateStr.length -1) { // 改变尾部剩余部分 rest = templateStr.substring(index) // 检测是否以数字和[开头 if (/^\d+\[/.test(rest)) { // 将数字入栈1 // 如果这个字符是数字，那么就将数字压入 stack1栈，把`空字符串压入stack2栈， let times = Number(rest.match(/^(\d+)\[/)[1]) stack1.push(times) // 将空字符串入栈2 stack2.push('') // 让指针后移 times这个数字多少就后移多少位 +1 // +1 是[括号 index += times.toString().length + 1 } else if (/^\w+\]/.test(rest)) { // 如果这个字符是字母，那么此时就把stack2栈顶这一项改为这个字母， let word = rest.match(/^(\w+)\]/)[1] // 字母和]开头 stack2[stack2.length-1] = word // 让指针后移 word这个数字多少就后移多少位 index += word.length } else if(rest[0] == ']'){ // 如果这个字符是]，那么就将数字从 stack1 栈中弹出，把 stack2的栈顶元素重复 stack1中弹栈的数字的次数`， // 然后将其从stack2中弹出，拼接到stack2的新栈顶上。 let times = stack1.pop() let word = stack2.pop() // repeat是h5中新增的方法比如： 'a'.repeat(2) = 'aa' stack2[stack2.length -1 ] += word.repeat(times) index++ } console.log(index, stack1,stack2); } // while遍历结束 stack1和stack2各剩一项 return stack2[0].repeat(stack1[0]) } console.log(smartRepeat('3[2[a]2[b]]'));

总结：词法分析的时候经常会用到栈的思路去解决问题。

手写 AST 抽象语法树 import parse from "./parse"; var templateStr = ` 你好 A B C ` let ast = parse(templateStr) console.log(ast);

我们知道AST抽象语法树如上图所示，所以我们需要就模板字符串转化为 AST抽象语法树，通过观察我们发现，其实这 AST抽象语法树的转换和上面栈的题目几乎差不多，都是要使用两个栈来进行运算，当遇到标签时进栈，遇到标签出栈。所以我们可以借助上面的题目栈的思路来完成 AST抽象语法树的转换。如果你真的理解上面的题目，这道题你理解起来很非常轻松！

parse（）方法

parse（）方法的作用通过栈思想来生成AST语法树

// index.js import parse from "./parse"; var templateStr = ` 你好 A B C ` let ast = parse(templateStr) console.log(ast); /** * 作用：用来生成AST抽象语法树 * @param {*} templateStr 传入的模板字符串 */ export default function parse(templateStr) { // 指针 var index = 0 // 栈1 存储标签 var stack1 = [] // 栈2 存储文字内容默认留一项不用判断stack2结束 var stack2 = [{'children':[]}] // 尾巴 var rest = templateStr // 开始正则 var startRegExp = /^\/ // 结束正则 var endRegExp = /^\/ // 文字正则 var wordErgExp = /^([^\ 0) { stack2[stack2.length - 1].children.push(pop_arr) } } else { new Error(stack1[stack1.length - 1] + '标签没有闭合') } // 指针跳过标签并包含所以要+3 index += tag.length + 3 } else if(wordErgExp.test(rest)) { // 检测到文字 let word = rest.match(wordErgExp)[1] // 文字不能是全空去除空格 if(!/^\s+$/.test(word)) { // 改变此时stack2栈顶元素 stack2[stack2.length - 1].children.push({'text': word, 'type': 3}) } index += word.length } else { index++ } } // console.log(stack2); return stack2[0].children[0] }

上面代码的过程，跟栈的算法过程一模一样，如果看不懂的小伙伴，可以再细读栈的例题，再来看这道题，保证你可以很很好的掌握和理解 AST抽象语法树的生成。当我们往标签中添加类名的时候，其实会报如下图的错误。

import parse from "./parse"; var templateStr = ` 你好 A B C ` let ast = parse(templateStr) console.log(ast);

其实原因很简单，就是在解析标签的时候，会默认将class="box box1" id="h3"也当成标签来处理，所以就会报错，即我们还需要将开始标签的正则进行完善

//修改开始正则，如果存在以空格除

【本文地址】

Vue 源码解析之AST抽象语法树

Vue 源码解析之AST抽象语法树

今日新闻

推荐新闻